package com.LeeCode;

import java.util.Arrays;

/**
 * 花期内花的数目
 */

public class Code2251 {
    public static void main(String[] args) {

    }

    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int n = flowers.length;
        int[] starts = new int[n];
        int[] ends = new int[n];

        for (int i = 0; i < n; i++) {
            starts[i] = flowers[i][0];
            ends[i] = flowers[i][1];
        }

        Arrays.sort(starts);
        Arrays.sort(ends);

        int m = people.length;
        int[] answer = new int[m];

        for (int i = 0; i < m; i++) {
            int t = people[i];

            // 找到 starts 中 <= t 的个数
            int started = upperBound(starts, t);

            // 找到 ends 中 < t 的个数
            int ended = upperBound(ends, t - 1);

            answer[i] = started - ended;
        }

        return answer;
    }

    // upperBound: 返回第一个 > target 的索引 → 即 <= target 的个数
    private int upperBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
